Prédiction de type on-policy par approximations¶
4. Méthodes de gradient stochastique et de semi-gradient¶
4.1. Principe de fonctionnement¶
Nous allons ici étudier des méthodes basées sur la descente stochastique du gradient (Stochastic Gradient Descent - SGD). Ces méthodes sont parmi les plus utilisées dans l'approximation des fonctions et sont particulièrement adaptées au problème de l'apprentissage par renforcement en ligne (de type on-policy).
Nécessité de la méthode SGD
Dans les méthodes de descente du gradient, les poids sont un vecteur colonne de dimension finie : $\textbf{w} = {\left( {{w_1},{w_2},...,{w_d}} \right)^T}$ et les fonctions des valeurs des états approximées $\hat v\left( {s,\textbf{w}} \right)$ son différentiables par rapport au poids $\textbf{w}$ pour tous les états $s \in S$. La valeur du vecteur $\textbf{w}$ est mise à jour à chaque pas de temps $t=0,1,2,3,...$, et donc on utilise la notation ${\textbf{w}_\textbf{t}}$ pour décrire la valeur du poids à chaque pas de temps.
Pour le moment, faisons l'hypothèse qu'à chaque pas de temps on observe un nouvel exemple qui à un état $S_t$ associe une valeur d'état $V_\pi$ en suivant la stratégie $\pi$ : ${S_t} \mapsto {V_\pi }\left( {{S_t}} \right)$ (les $S_t$ peuvent être sélectionnés de manière aléatoire). Même si nous donnons les valeurs exactes pour chaque état, il persiste une difficulté car les fonctions d'approximation ont une résolution limitée. En particulier, il n'existe pas en général de valeur du poids $\textbf{w}$ permettant d'avoir tous les états correctement estimés par les fonctions d'approximations. De plus, il faut généraliser cette mise à jour à l'ensemble des états de l'environnement ne sont pas apparus dans cet exemple.
Fonctionnement de la méthode SGD
Faisons l'hypothèse que les états apparaissent dans nos exemples avec la même distribution $\mu$ et que nous essayons de minimiser notre fonction objectif $\overline {VE}$ :
Une bonne stratégie dans ce cas et d'essayer de minimiser l'erreur d'approximation sur l'ensemble des exemples observés. La méthode SGD réalise cela en ajustant le vecteur poids après chaque exemple par une petite quantité qui correspond à proportion de la dérivée de l'erreur :
$\alpha$ est un paramètre positif permettant de régler la dynamique de la mise à jour et est appelé le taux d'apprentissage. $\nabla f\left( \textbf{w} \right)$ décrit la dérivée partielle de la fonction scalaire $f$ par rapport à chacune des composantes du vecteur $\textbf{w}$. C'est le gradient de f par rapport à $\textbf{w}$ :
Les méthodes SGD sont de type descente du gradient car la correction effectuée sur l'erreur à chaque pas de temps est proportionnelle à la part négative du gradient de la fonction d'erreur. Ces méthodes sont dites stochastiques lorsque les mises à jour sont réalisées, comme c'est le cas ici, sur un unique exemple (qui peut avoir été sélectionné de manière aléatoire).
Rappelons encore une fois que nous ne cherchons pas à obtenir les vraies valeurs $V_\pi$ mais les meilleures approximations possibles, c'est-à-dire de trouver un optimum local. La convergence vers un optimum local est assurée si le taux d'apprentissage $\alpha$ décroit au fur et à mesure des pas de temps des calculs.
Situation où les valeurs réelles des états ne sont pas connues
Considérons maintenant que les vraies valeurs des états ne sont pas connues et que nous n'avons qu'une estimation de la cible. Notons $U_t$ cette estimation réalisée à l'instant $t$. L'exemple observé fait donc une association de la forme ${S_t} \mapsto {U_t}$. $U_t$ peut-être par exemple une version bruitée de $V_\pi(S_t)$, ou encore une valeur obtenue par une méthode qui "bootstrap" comme par exemple les méthodes par différences temporelles que nous avons étudiées dans la formation d'initiation à l'apprentissage par renforcement.
Dans ce cas, il est impossible de réaliser une mise à jour exacte du vecteur poids $\textbf{w}$ mais une approximation de celui-ci en substituant $U_t$ à la place de $V_\pi(S_t)$ :
Si $U_t$ est une estimation non biaisée, c'est-à-dire que $E\left[ {{U_t}|{S_t} = s} \right] = {V_\pi }\left( {{S_t}} \right)$ pour tous les pas de temps $t$, alors la convergence de ${\textbf{w}_\textbf{t}}$ vers un optimum local est assurée (sous réserve de la décroissance du taux d'apprentissage $\alpha$).
4.2 Application aux méthodes de Monte-Carlo¶
Supposons que l'agent suive une stratégie $\pi$ dans un environnement et génère des exemples de trajectoires. Avec la méthode de Monte-Carlo, la cible $G_t$ est construite comme étant la valeur moyenne des revenus obtenus en suivant cette trajectoire. Dans ce cas, cette cible est donc une estimation non biaisée de $V_\pi(S_t)$. La méthode SGD converge donc vers un optimum local qui permet d'approximer $V_\pi(S_t)$.
L'algorithme illustre la manière d'implanter la méthode SGD dans le cas de Monte-Carlo :
4.3 Application aux méthodes qui bootstrap¶
Pour les méthodes qui réalisent une estimation de la valeur des états avant la fin de l'épisode, comme par exemple les méthodes par différence temporelle, la garantie de convergence n'est plus assurée. En effet, la cible ${G_{t:t + n}}$ pour la méthode n-step ou encore la cible $\sum\nolimits_{a,s',r} {\pi \left( {a|{S_t}} \right)p\left( {s',r|{S_t},a} \right)\left[ {r + \gamma \hat v\left( {s',{\textbf{w}_\textbf{t}}} \right)} \right]}$ pour la méthode par programmation dynamique dépend de la valeur courante du vecteur poids ${\textbf{w}_\textbf{t}}$. Cela implique donc qu'il y aura un biais car les équations de mise à jour de la méthode SGD dépendent également de cette valeur.
Ces méthodes d'apprentissage par renforcement qui "bootstrap" ne sont donc pas des méthodes pouvant être traitées avec la vraie version de l'algorithme SGD. Pour celle-ci, on utilise plutôt les méthodes du semi-gradient.
Bien que les méthodes de semi-gradient ne convergent pas de manière aussi robuste que les vraies méthodes par descente du gradient, elles convergent cependant dans de nombreux cas comme par exemple dans les cas linéaires que nous allons étudier par la suite. De plus, elles apportent de nombreux avantages ce qui fait qu'elles sont souvent choisies. Par exemple, elles permettent de réaliser un apprentissage plus rapide et de réaliser un apprentissage en ligne, sans avoir à attendre la fin d'un épisode.
L'algorithme ci-dessous illustre la manière d'implanter la méthode de semi-gradient dans le cas de TD(0) :
4.4 Technique par agrégation des états¶
La technique d'agrégation des états est une forme généralisée d'approximation des fonctions dans laquelle les états de l'environnement sont regroupés par lot. Chaque lot se voit alors attribuer une des composante du vecteur poids $\textbf{w}$. La valeur de chaque état est alors estimée comme étant une valeur unique propre à l'ensemble des états du lot, et chaque fois d'un lot d'états est mis à jour, les autres lots ne sont pas concernés.
La technique d'agrégation des états est un cas particulier de la méthode SGD pour laquelle le gradient prend la valeur suivante :
- $\nabla \hat v\left( {{S_t},\textbf{w}_\textbf{t}} \right) = 1$ si les états sont dans le lot traité par la composante du vecteur poids
- $\nabla \hat v\left( {{S_t},\textbf{w}_\textbf{t}} \right) = 0$ sinon
